package com.kobeliu.entity;

/**
 * @Author: Kobe_Liu
 * @Date: 2021/12/3 9:51
 */

import java.util.Arrays;

/**
 * 给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
 *
 *     选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
 *
 * 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
 *
 * 以这种方式修改数组后，返回数组 可能的最大和 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [4,2,3], k = 1
 * 输出：5
 * 解释：选择下标 1 ，nums 变为 [4,-2,3] 。
 *
 * 示例 2：
 *
 * 输入：nums = [3,-1,0,2], k = 3
 * 输出：6
 * 解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。
 *
 * 示例 3：
 *
 * 输入：nums = [2,-3,-1,5,-4], k = 2
 * 输出：13
 * 解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。
 */
public class Demo_63_No1005 {

    public static void main(String[] args) {

        int[] nums = new int[]{-8,3,-5,-3,-5,-2};

        int i = largestSumAfterKNegations(nums, 6);
        System.out.println(i);


    }

    /**
     * 先排序，优先将<0 变成 >0
     * 之后若还有次数，就将数组再次排序，
     * 拿最小的非负数 进行正负变化，使数组的sum 始终保持最大
     * @param nums
     * @param k
     * @return
     */
    public static int largestSumAfterKNegations(int[] nums, int k) {
        //数组从小到大排序
        Arrays.sort(nums);
        int len = nums.length;
        int i = 0;
        if(k<len){
            for (; i < k; i++) {
                if(nums[i]<0){
                    nums[i] = -nums[i];
                }else{
                    break;
                }
            }
        }else{
            for (; i < len; i++) {
                if(nums[i]<0){
                    nums[i] = -nums[i];
                }else{
                    break;
                }
            }
        }

        i -= k;
        int sum = 0;
        //再排序，将最小值进行变号
        Arrays.sort(nums);
        if(i%2!=0){
            nums[0] = -nums[0];
        }
        //是偶数
        for (int j = 0; j < nums.length; j++) {
            sum += nums[j];
        }

        return sum;

    }
}
